# 76. 最小覆盖子串
from collections import Counter


def minWindow(s: str, t: str) -> str:
    # 判断两个字符串是否为子串关系
    def contain_sub(source_dict: dict, sub_dict: dict) -> bool:
        """
        判断字符串中是否包含子串
        :param source_dict:  字符串
        :param sub_dict: 子串
        :return: True表示包含，False表示不包含
        """
        re = True
        for key, value in sub_dict.items():
            if not re:
                return False
            if key not in source_dict:
                return False
            re = source_dict[key] >= value
        return re

    # 窗口的左指针
    left_index = 0
    # 窗口的右指针
    right_index = 0
    # 窗口的 dict
    window_dict = {}
    t_dict = dict(Counter(t))

    print(f"t_dict:{t_dict}")

    # 字符串的长度
    s_len = len(s)

    # 窗口大小
    min_sub_str = ''

    # 右指针一直往右边移动，找到了之后，左指针往左移动
    while left_index <= right_index < s_len:
        right_char = s[right_index]
        # 放入 dict
        if right_char in window_dict:
            window_dict[right_char] += 1
        else:
            window_dict[right_char] = 1

        # 判断是否包含子串
        # 如果包含，左边的指针往右边移动
        while contain_sub(window_dict, t_dict):
            contain_sub_str = s[left_index:right_index + 1]
            if len(min_sub_str) == 0:
                min_sub_str = contain_sub_str
            elif len(min_sub_str) > len(contain_sub_str):
                min_sub_str = contain_sub_str
            left_char = s[left_index]
            window_dict[left_char] -= 1
            left_index += 1

        right_index += 1

    return min_sub_str


result = minWindow("ADOBECODEBANC", "ABC")
print(f"result:{result}")

result = minWindow("a", "a")
print(f"result:{result}")

result = minWindow("a", "aa")
print(f"result:{result}")

result = minWindow("XDOBECODEBANC", "XBC")
print(f"result:{result}")
